package 十大排序算法;

public class 希尔排序 {
    private void shellSort(int[] a){
        int dk = a.length/2;
        while (dk>=1){
         ShellinsertSort(a,dk);
         dk = dk/2;
        }
    }

    private void ShellinsertSort(int[] a, int dk) {
        //类似插入排序，只是插入排序增量是 1，这里增量是 dk,把 1 换成 dk 就可以了
        for (int i = dk; i < a.length; i++) {
            if (a[i-dk]>a[i]){
                int j;
                int x = a[i]; //x为待插入元素
                a[i] = a[i-dk];
                for ( j = i-dk; j >= 0&&x<a[j]; j=j-dk) {
                    //逐一往后面找到要插入的位置
                    a[j+dk] = a[j];
                }
                a[j+dk] = x;//插入
            }
        }
    }
}
